#include <bits/stdc++.h>
using namespace std;



class Solution
{
public:
    int n;
    vector<string> ans;
    string mp[10] = {"", "", "abc", "def", "ghi","jkl", "mno","pqrs","tuv","wxyz"};
    string tmp;
    void dfs(int x, string & digits) //x为层数
    {
        if (x == n)
        {
            ans.emplace_back(tmp);
            return;
        }
        for (auto &t : mp[digits[x] - '0'])
        {
            tmp[x] = t;
            dfs(x + 1, digits);
        }
    }
    vector<string> letterCombinations(string digits)
    {
        n = digits.size();
        if (n == 0)
        {
            return {};
        }
        tmp.resize(n);
        dfs(0, digits);
        return ans;
    }
};
